//https://leetcode.cn/problems/binary-watch/
package codeRandomThoughts.Test401二进制手表;

import java.util.ArrayList;
import java.util.List;

public class Solution {
    int hourSum = 0;
    int minSum = 0;
    List<String> result = new ArrayList<>();

    public List<String> readBinaryWatch(int turnedOn) {
        int[] led = {8, 4, 2, 1, 32, 16, 8, 4, 2, 1};
        int index = 0;
        int count = 0;
        backtracking(turnedOn, index, count, led);
        return result;
    }

    public void backtracking(int turnedOn, int index, int count, int[] led) {
        //剪枝
        if (hourSum > 11 || minSum > 59) {
            return;
        }
        //终止条件
        if (count == turnedOn) {
            if (minSum < 10) {
                result.add(hourSum + ":0" + minSum);
            } else {
                result.add(hourSum + ":" + minSum);
            }
            return;
        }

        //单层循环逻辑
        for (int i = index; i < 10; i++) {
            if (i < 4) {
                hourSum += led[i];
            } else {
                minSum += led[i];
            }
            count++;
            backtracking(turnedOn, i + 1, count, led);
            count--;
            if (i < 4) {
                hourSum -= led[i];
            } else {
                minSum -= led[i];
            }
        }
    }
}
